package com.code.test.first.greedy;

import java.util.stream.IntStream;
import java.util.Arrays;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.md
 * <p>
 * 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
 * <p>
 * 以这种方式修改数组后，返回数组可能的最大和。
 * <p>
 * 示例 1：
 * <p>
 * 输入：A = [4,2,3], K = 1
 * 输出：5
 * 解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。
 * 示例 2：
 * <p>
 * 输入：A = [3,-1,0,2], K = 3
 * 输出：6
 * 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
 * 示例 3：
 * <p>
 * 输入：A = [2,-3,-1,5,-4], K = 2
 * 输出：13
 * 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
 * 提示：
 * <p>
 * 1 <= A.length <= 10000
 * 1 <= K <= 10000
 * -100 <= A[i] <= 100
 */
public class Code1005 {

    public static void main(String[] args) {
        int[] nums = {-5,-4,-3,-2,-1};
        int ret = max2(nums, 3);
        System.out.println(ret);
    }


    public static int max(int[] nums, int k) {
        int ret = 0;
        //从小到大排序
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
            if (k == 0) {
                break;
            }
        }

        if (k > 0) {
            Arrays.sort(nums);
            for (int i = 0; i < k; i++) {
                //上面已经把负数反转，这里需要把最小正数翻转,
                //因为没有限制同一个元素的翻转次数，所以一直翻转最小的那个
                nums[0] = -nums[0];

            }
        }

        for (int i = 0; i < len; i++) {
            ret += nums[i];
        }
        return ret;
    }

    public static int max2(int[] nums, int K) {
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        //这里是为了让前面的负数，都直接变为正数
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int len = nums.length;
        //如果数组都是正数，则这里不变,k只要一直翻转最小的数
        //如果数组有正有负，这里翻转的元素个数为x个，x<=k，此时不管k剩下多少个，只需要翻转最小的那个数
        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }
        // 如果K还大于0，那么反复转变数值最小的元素，将K用完
        //然后，这里如果k还存在，看k是奇数还是偶数，如果是奇数，则反转最后一个元素

        //如果k为偶数，则说明偶数次反转最后一个元素也是不变
        /**
         * 本质上只有2种情况
         * 负数 n <= k,这种代表翻转完k还有剩，则把剩下的k一直翻转最小的数:nums[len-1]=-nums[len-1]
         * 负数 n > k,这种代表翻转完k没有剩，直接统计
         */
        if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
        return Arrays.stream(nums).sum();
    }


    public static int maxx(int[] nums, int k){
        Arrays.sort(nums);
        for(int i=0;i<k;i++) {
            nums[0] = -nums[0];
            Arrays.sort(nums);
        }
        return Arrays.stream(nums).sum();
    }

}
